#lang sicp
(define (memorize f)
  (let ((table (make-table)))
    (define put (table 'insert!-proc))
    (define get (table 'lookup-proc))
    (lambda args
      (let ((res (get args)))
        (if res
            res
            (let ((res (apply f args)))
              (put args res)
              res))))))

(define (make-table)
  (define table (list '*table*))
  (define same-key? equal?)

  (define (make-record key val)
    (list (cons key val)))
  (define (value-record record)
    (cdar record))
  (define (key-record record)
    (caar record))
  (define (set-value-record! record value)
    (set-cdr! (car record) value))

  (define (lookup keys)
    (define (iter table keys)
      (if (null? keys)
          (value-record table)
          (let ((record (assoc (cdr table) (car keys))))
            (if record
                (iter record (cdr keys))
                #F))))
    (if (null? keys)
        (error "require keys -- lookup - make-table")
        (iter table keys)))

  (define (insert! keys value)
    (define (iter table keys)
      (if (null? keys)
          (set-value-record! table value)
          (let ((record (assoc (cdr table) (car keys))))
            (if record
                (iter record (cdr keys))
                (let ((record (make-record (car keys) #F)))
                  (set-cdr! table (cons record (cdr table)))
                  (iter record (cdr keys)))))))
    (if (null? keys)
        (error "")
        (iter table keys))
    'ok)

  (define (assoc table key)
    (find table (lambda (record)
                  (same-key? (key-record record)
                             key))))

  (define (dispatch m)
    (cond ((eq? m 'insert!-proc) insert!)
          ((eq? m 'lookup-proc) lookup)
          (else
           (error "Unknown message! -- dispatch - make-table" m))))
  dispatch)


(define (find se predicate?)
  (cond ((null? se) #F)
        ((predicate? (car se)) (car se))
        (else
         (find (cdr se) predicate?))))




(define (fib n)
  (cond ((= n 1) 1)
        ((= n 0) 0)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

(define test
  (memorize (lambda (n) n)))


(define memo-fib
  (memorize (lambda (n)
              (cond ((= n 0) 0)
                    ((= n 1) 1)
                    (else
                     (+ (memo-fib (- n 1))
                        (memo-fib (- n 2))))))))


(define (iter-fib n)
  (define (iter cur next index)
    (if (= index n)
        cur
        (iter next (+ cur next) (inc index))))
  (iter 0 1 0))
